package woa.linkedlist;

/**
 * 旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 *
 * @author wangpeng
 * @date 2021/11/22
 */
public class RotateRightProblem {

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode slow = sentinel, fast = sentinel;
        while (fast.next != null) {
            if (k > 0) {
                fast = fast.next;
                if (fast.next == null) {
                    fast = sentinel;
                }
                k--;
            } else {
                slow = slow.next;
                fast = fast.next;
            }
        }

        fast.next = head;
        head = slow.next;
        slow.next = null;

        return head;
    }

    public static ListNode rotateRight1(ListNode head, int k) {
        if (head == null) return null;
        ListNode tail = head;
        int t = 1;
        while (tail.next != null) {
            t++;
            tail = tail.next;
        }

        k = t - k % t;
        while (k > 0) {
            tail.next = head;
            tail = tail.next;
            ListNode next = head.next;
            head.next = null;
            head = next;
            k--;
        }

        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        rotateRight1(head, 2);
    }
}
